//旋转数组
class Solution {
public:
    /**
     * 旋转数组
     * @param n int整型 数组长度
     * @param m int整型 右移距离
     * @param a int整型vector 给定数组
     * @return int整型vector
     */
    vector<int> solve(int n, int m, vector<int>& a) {
        // write code here
        //三步逆置法
        m %= a.size();
        reverse(a.begin(),a.begin()+n-m); //前n-m个元素逆置
        reverse(a.begin()+n-m,a.end());//后m个元素逆置
        reverse(a.begin(),a.end());//整体逆置
        return a;
    }
};


//合并区间
class Solution {
public:

    vector<Interval> merge(vector<Interval> &arr) {
        vector<Interval> ans;
        if(arr.size() == 0)
            return ans;
        sort(arr.begin(),arr.end(),[](const Interval& l,Interval& r){
            return l.start < r.start; //根据左端点排升序
        });  
        int start = arr[0].start,end = arr[0].end;
        for(int i = 1;i<arr.size();i++)
        {
            if(end >= arr[i].start)
            {
                end = max(end,arr[i].end);
            }
            else 
            {
                ans.push_back(Interval(start,end));
                start = arr[i].start;
                end = arr[i].end;
            }
        }
        ans.push_back(Interval(start,end));
        return ans;
    }
};

//杨辉三角
class Solution {
public:
    vector<vector<int>> generate(int numRows) {
        vector<vector<int>> ans(numRows,vector<int>());
        for(int i = 0;i<numRows;i++)
        {
            ans[i].resize(i+1,0);
            ans[i][0] = ans[i][ans[i].size()-1] = 1; //每一行的第一个元素和最后一个元素值为1
        }
        for(int i = 0;i<ans.size();i++)
        {
            for(int j = 0;j<ans[i].size();j++)
            {
                if(ans[i][j] == 0)
                    ans[i][j] = ans[i-1][j] + ans[i-1][j-1];
            }
        }
        return ans;
    }
};
//写法2:
for(int i = 0;i<ans.size();i++)
{
    for(int j = 1;j<ans[i].size()-1;j++)
    {
        ans[i][j] = ans[i-1][j] + ans[i-1][j-1];
    }
}
